package com.mikesamuel.dateseries.shared;

import java.util.ArrayList;
import java.util.Collection;
import java.util.EnumSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * Given a few dates, infer a periodic function that produces those dates and
 * possibly others.
 */
public class Inference {
  public final List<Day> dates;
  public final DateSeries.Specification rule;
  public final double confidence;

  public Inference(Collection<? extends Day> idates, final WeekDay wkst) {
    this.dates = new ArrayList<Day>(new TreeSet<Day>(idates));
    if (this.dates.isEmpty()) {
      this.rule = null;
      this.confidence = 0;
      return;
    }
    final Day firstDate = dates.get(0);
    final Day firstWeek = DateUtil.startOfWeek(firstDate, wkst);
    int nDates = dates.size();

    List<Day> years = mapDates(
       dates,
       new DayFn() {
         public Day apply(Day d) { return new Day(d.year(), 1, 1); }
       });
    List<Day> months = mapDates(
       dates,
       new DayFn() {
         public Day apply(Day d) {
           return d.withDay(1);
         }
       });
    List<Day> weeks = mapDates(
       dates,
       new DayFn() {
         public Day apply(Day d) {
           return d.withDay(d.day() - ((7 + d.dayOfWeek().minus(wkst)) % 7));
         }
       });
    List<Day> days = dates;

    EnumSet<WeekDay> daysOfWeekSet = EnumSet.noneOf(WeekDay.class);
    Map<Integer, List<Integer>> monthDaysToDateIndices =
      new TreeMap<Integer, List<Integer>>();
    for (int i = 0; i < nDates; ++i) {
      Day d = dates.get(i);
      daysOfWeekSet.add(d.dayOfWeek());
      int dom = d.day();
      int nDays = DateUtil.daysInMonth(d.year(), d.month());
      int ndom = nDays - dom - 1;
      multimapAdd(monthDaysToDateIndices, dom, i);
      multimapAdd(monthDaysToDateIndices, ndom, i);
    }
    final WeekDay[] daysOfWeek = daysOfWeekSet.toArray(new WeekDay[0]);
    final int[] daysOfMonth = toPrimArray(computeGreedySetCover(
        monthDaysToDateIndices));

    final HashSet<Day> dateSet = new HashSet<Day>(dates);
    class Scorer {
      DateSeries.Specification lastCandidate = null;
      DateSeries.Specification bestCandidate = null;
      double bestScore = Double.NEGATIVE_INFINITY;

      private double scoreOf(DateSeries.Specification candidate) {
        candidate.wkst = wkst;
        int nMatches = 0;
        int nDates = dates.size();
        DateSeries series = new DateSeries(firstDate, candidate);
        Iterator<Day> it = series.iterator();
        for (int i = 0; i < nDates && it.hasNext(); ++i) {
          if (dateSet.contains(it.next())) {
            ++nMatches;
          }
        }
        return ((double) nMatches) / nDates;
      }

      void consider(DateSeries.Specification... candidates) {
        for (DateSeries.Specification candidate : candidates) {
          if (bestScore == 1) { return; }
          if (lastCandidate != null && lastCandidate.equals(candidate)) {
            continue;
          }
          lastCandidate = candidate;
          double score = scoreOf(candidate);
          if (bestScore < score) {
            bestCandidate = candidate;
            bestScore = score;
          }
        }
      }

      private DateSeries.Specification spec(
          Freq f, int interval, WeekDay[] daysOfWeek, int[] daysOfMonth) {
        DateSeries.Specification spec = new DateSeries.Specification();
        spec.frequency = f;
        spec.interval = interval;
        spec.daysOfWeek = daysOfWeek;
        spec.daysOfMonth = daysOfMonth;
        return spec;
      }

      void considerForFreq(Freq freq, int interval) {
        consider(
            spec(freq, interval, null, null),
            spec(freq, interval, daysOfWeek, null),
            spec(freq, interval, null, daysOfMonth),
            spec(freq, interval, daysOfWeek, daysOfMonth));
      }
    }

    Scorer scorer = new Scorer();

    scorer.consider(new DateSeries.Specification());

    if (years.size() > 1) {
      int yearInterval = minInterval(
        years,
        new DayToIntFn() {
          public int apply(Day d) { return d.year(); }
        });
      scorer.considerForFreq(Freq.YEARLY, yearInterval);
    }

    if (months.size() > 1) {
      int monthInterval = minInterval(
        months,
        new DayToIntFn() {
          public int apply(Day d) { return d.year() * 12 + d.month(); }
        });
      scorer.considerForFreq(Freq.MONTHLY, monthInterval);
    }

    if (weeks.size() > 1) {
      int weekInterval = minInterval(
        weeks,
        new DayToIntFn() {
          public int apply(Day d) {
            return DateUtil.daysBetween(d, firstWeek) / 7;
          }
        });
      scorer.considerForFreq(Freq.WEEKLY, weekInterval);
    }

    {
      int dayInterval = minInterval(
        days,
        new DayToIntFn() {
          public int apply(Day d) {
            return DateUtil.daysBetween(d, firstDate);
          }
        });
      scorer.considerForFreq(Freq.DAILY, dayInterval);
    }

    this.rule = scorer.bestCandidate;
    this.confidence = scorer.bestScore;
  }

  private static <K, V> void multimapAdd(Map<K, List<V>> m, K k, V v) {
    List<V> values = m.get(k);
    if (values == null) {
      values = new ArrayList<V>();
      m.put(k, values);
    }
    values.add(v);
  }

  private interface DayFn {
    Day apply(Day d);
  }

  private static List<Day> mapDates(Iterable<Day> days, DayFn f) {
    TreeSet<Day> out = new TreeSet<Day>();
    for (Day d : days) {
      out.add(f.apply(d));
    }
    return new ArrayList<Day>(out);
  }

  private interface DayToIntFn {
    int apply(Day d);
  }

  private static int minInterval(Iterable<Day> days, DayToIntFn toInt) {
    Iterator<Day> it = days.iterator();
    if (!it.hasNext()) { return 1; }
    int last = toInt.apply(it.next());
    if (!it.hasNext()) { return 1; }
    int minInterval = Integer.MAX_VALUE;
    do {
      int curr = toInt.apply(it.next());
      int interval = curr - last;
      if (interval < minInterval) { minInterval = interval; }
      last = curr;
    } while (it.hasNext());
    return minInterval;
  }

  private static <K, V, C extends Collection<V>> List<K> computeGreedySetCover(
      Map<K, C> keyToSetIds) {
    List<K> out = new ArrayList<K>();
    while (true) {
      K largestKey = null;
      int largestKeyCount = 0;
      for (Map.Entry<K, C> e : keyToSetIds.entrySet()) {
        int keyCount = e.getValue().size();
        if (keyCount > largestKeyCount) {
          largestKeyCount = keyCount;
          largestKey = e.getKey();
        }
      }
      if (largestKeyCount == 0) { break; }
      out.add(largestKey);
      Collection<V> covered = keyToSetIds.remove(largestKey);
      Iterator<Map.Entry<K, C>> it = keyToSetIds.entrySet().iterator();
      while (it.hasNext()) {
        Map.Entry<K, C> e = it.next();
        C v = e.getValue();
        v.removeAll(covered);
        if (v.isEmpty()) { it.remove(); }
      }
    }
    return out;
  }

  private static int[] toPrimArray(List<Integer> ints) {
    int n = ints.size();
    int[] arr = new int[n];
    for (int i = 0; i < n; ++i) {
      arr[i] = ints.get(i);
    }
    return arr;
  }
}